package com.exercises;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Exercise815 {
    public static void main(String[] args) {

        int[][] routes = new int[2][3];
        routes[0] = new int[]{1, 2, 7};
        routes[1] = new int[]{3, 6, 7};
        System.out.println(numBusesToDestination(routes, 1, 6));
    }


    public static int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;

        int length = routes.length;
        //线路i,j是否互通
        boolean[][] edge = new boolean[length][length];
        //站点key包含那几条线路
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            for (int site : routes[i]) {
                List<Integer> routeList = map.getOrDefault(site, new ArrayList<>());
                for (Integer j : routeList) {
                    edge[i][j] = edge[j][i] = true;
                }
                routeList.add(i);
                map.put(site, routeList);
            }
        }
        int[] dis = new int[length];
        Arrays.fill(dis, -1);
        Queue<Integer> que = new LinkedList<Integer>();
        for (int route : map.getOrDefault(source, new ArrayList<Integer>())) {
            //包含起始站的线路value=1;
            dis[route] = 1;
            que.offer(route);
        }
        while (!que.isEmpty()) {
            int i = que.poll();
            for (int j = 0; j < length; j++) {
                //依次给相邻的线路算从soure出来的value
                if (edge[i][j] && dis[j] == -1) {
                    dis[j] = dis[i] + 1;
                    que.offer(j);
                }
            }
        }
        int result = Integer.MAX_VALUE;
        for (int value : map.getOrDefault(target, new ArrayList<>())) {
            result = Math.min(result, dis[value]);
        }

        return result == Integer.MAX_VALUE ? -1 : result;
    }


}
